package dp.pack;

import dp.Common;

/**
 * @author : Rookie
 * @description :
 * @date : 2023/8/17
 */
public class SpecifyItemCount {

    public static int getMaxValue(int[] weights, int[] values, int capacity, int itemNum) {
        // dp[i][j][k] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包,并且已经装了k件物品，价值总和最大是多少
        int[][][] dp = new int[weights.length + 1][capacity + 1][itemNum + 1];
//
//        // 初始化边界条件：没有物品或者背包容量为0时，无论需要装多少件物品，价值都是0
//        for (int i = 0; i <= weights.length; i++) {
//            for (int k = 0; k <= itemNum; k++) {
//                dp[i][0][k] = 0;
//            }
//        }
//
//        // 初始化第一列：当背包容量大于0但物品数量为0时，价值也为0
//        for (int j = 1; j <= capacity; j++) {
//            dp[0][j][0] = 0;
//        }

        for (int i = 1; i <= weights.length; i++) {
            for (int j = 1; j <= capacity; j++) {
                for (int k = 1; k <= itemNum; k++) { // 注意这里k的范围，不能超过当前剩余可选物品数量
                    if (weights[i - 1] > j) {
                        dp[i][j][k] = dp[i - 1][j][k];
                    } else {
                        dp[i][j][k] = Math.max(dp[i - 1][j][k], dp[i - 1][j - weights[i - 1]][k - 1] + values[i - 1]);
                    }
                }
            }
        }
        Common.print3dArr(dp);
        return dp[weights.length][capacity][itemNum];
    }

    /**
     * 滚动数组解决
     * @param weights
     * @param values
     * @param capacity
     * @param itemNum
     * @return
     */
    public static int getMaxValue2(int[] weights, int[] values, int capacity, int itemNum) {
        // dp[j][k] 表示将前i个物品中的k件物品放入容量为j的背包，最大价值为多少
        int[][] dp = new int[capacity + 1][itemNum + 1];

        // 初始化边界条件...

        for (int i = 1; i <= weights.length; i++) { // 遍历物品
            for (int k = itemNum; k > 0; k--) { // 倒序遍历已选择物品数量
                for (int j = capacity; j >= weights[i - 1]; j--) { // 倒序遍历背包容量
                    dp[j][k] = Math.max(dp[j][k], dp[j - weights[i - 1]][k - 1] + values[i - 1]);
                }
            }
        }

        return dp[capacity][itemNum];
    }

    public static void main(String[] args) {
        int[] weights = {2, 3, 4, 5, 6}; // 物品的重量
        int[] values = {4, 6, 8, 9, 10}; // 物品的价值
        int capacity = 15; // 背包容量
        int itemNum = 3; // 需要装的物品件数
        int maxValue = getMaxValue2(weights, values, capacity, itemNum);
        System.out.println("背包容量为 "+capacity+" 的情况下，装入指定的 "+itemNum+" 件物品的最大价值为：" + maxValue);
    }
}
